Wrogie Państwa

Limit pamięci: 64 MB

Bitocja i Bajtocja planują podpisać rozejm po długotrwałej wojnie. Państwa te muszą zdecydować, do kogo będą należeć poszczególne miasta. Władcy Bitocji i Bajtocji postanowili, że dokonają podziału tak, aby zminimalizować liczbę bezpośrednich połączeń między parami miast, należącymi do różnych państw.

Twoim zadaniem jest podanie wspomnianej wyżej liczby po podpisaniu rozejmu.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite i (), oznaczające odpowiednio liczbę miast oraz liczbę połączeń. Drugi wiersz wejścia zawiera ciąg liczb całkowitych (). Jeżeli ma wartość 1, to miasto należeć będzie do Bitocji, 2, to miasto należeć będzie do Bajtocji, 3, to miasto należy przydzielić albo do Bajtocji albo do Bitocji. Kolejnych wierszy zawiera opisy połączeń między miastami. Każdy wiersz opisu zawierać będzie dwie liczby , , () oznaczające, że miasta i są połączone bezpośrednią drogą. Żadna para (, ) się nie powtórzy.

Możesz założyć, że w testach wartych około punktów zachodzi dodatkowy warunek

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie połączeń między miastami należącymi do Bitocji i Bajtocji po podpisaniu rozejmu.

Przykład

Dla danych wejściowych:

4 4
1 1 3 2
1 2
1 3
2 3
3 4

poprawną odpowiedzią jest:

1

Wyjaśnienie do przykładu: Jeżeli miasto numer 3 zostanie przydzielone Bitocji, to występować będzie tylko jedno połączenie między miastami Bitocji i Bajtocji - między miastami 3 i 4.

Autor zadania: Joanna Bujnowska (zapożyczenie).